The present invention relates generally to cryptographic primitives and more particularly, to public-key (asymmetric) cryptographic systems and digital signature algorithms that are based on paraunitary matrices.
The principal of public-key cryptography involves exchanging information between parties without requiring a secure channel. Public-key cryptography is different from secret-key cryptosystems in which both parties must share a secret key. In a public-key system, each party has a pair of secret and public keys. Everyone can send encrypted message to a designated party using its public key. However, only the designated party can decrypt using his corresponding secret key. Public-key systems are used for the exchange or the distribution of secret keys that are used in symmetric cryptosystems. Except for the key exchange, other applications of public-key cryptography are digital signature and data authentication schemes. A well-known public-key cryptosystem, RSA, uses a univariate monomial over a very large ring. The public key consists of the exponent of a monomial and a composite number obtained by multiplying two large prime numbers. The security of RSA is believed to be based on the problem of factoring large composite numbers. Although after its conception in 1978, RSA has not been broken yet, there are some practical problems in its implementation. The first problem is the key-setup time that is too long for computationally-limited processors used in some applications such as pervasive computing. For example, it takes tens of minutes on a Palm V that uses a 16.6 MHz Dragonball processor to generate 1024 bits RSA key. Another problem is the size of the key that is too long in applications where bandwidth is limited. It must also be increased every year because of improvements in the factorization algorithms and computational power. Currently, the minimum recommended size of RSA key is 1024 bits. As suggested by Schneier in Applied Cryptography: Protocols, Algorithms, and Source Code in C.” 2nd ed. New York, Wiley. 1996, the minimum size must be 4096 bits by 2015 and 8192 bits by 2025. This implies more complicated computations and longer key-setup time in the future.
In an attempt to remedy these problems, two paths are taken: 1) using monomials as the public key and hiding information in the exponent that leads to the discrete logarithm over complicated groups (e.g., points on elliptic curves) and 2) considering multivariate polynomials over small fields (e.g., GF(2m) for some small m). Comparing to RSA, systems based on the discrete logarithm over elliptic curves are able to maintain the same security level with shorter key sizes. Hence, elliptic curve cryptography (ECC) seems to be suitable for devices with low computational power such as smart cards. However, ECC also has some problems and drawbacks. The shortest signature that one can generate using an elliptic curve digital signature algorithm (ECDSA) is 320 bits, which is still long for many applications. Elliptic curves over fields of characteristic two can be easily implemented in hardware, but in order to maintain security, one must employ a very large finite field, which implies a long signature. The Koblitz curves are special elliptic curves used to reduce the complexity of ECC. However, some cryptographers are concerned that the special structure in these curves (to facilitate an efficient implementation) may actually be used to efficiently attack them. Another problem is the complexity of the elliptic curve signature-verification algorithm. A comparison between ECDSA and RSA in a field with prime characteristic shows that for practical sizes of fields and moduli, signature verification with ECDSA is 40 times slower than that using RSA.
Considering the shortcomings of the RSA and ECDSA, it would be desirable to have practical cryptosystems based on problems other than the assumptions currently in use. One might be in a safer state against possibilities such as the emergence of an efficient algorithm for factoring or computing discrete logarithms. An alternative approach is multivariate cryptography that includes systems based on multivariate polynomials over small fields. Multivariate cryptography is considered to be the cryptography of the 21st century. Cryptosystems based on multivariate polynomials over small fields are faster than RSA and ECC. These are schemes whose public information is a set of multivariate polynomials. Their security is based on the difficulty of solving systems of multivariate polynomial equations. The main challenge in designing such systems is including a trapdoor in the public polynomials without using polynomials with very specific forms. However, systems of random polynomials are usually very hard to invert as this difficulty is the security basis of multivariate cryptosystems. To solve this paradigm, schemes have been proposed whose public polynomials are attempted to look random while the special structure is somehow hidden from the view of cryptanalyst. For example, hidden field equations (HFE) scheme uses a quadratic univariate monomial over an extension field of a small finite field. The representation of the monomial over the small field gives a set of quadratic homogenous polynomials. Unfortunately, this scheme and many of its variants have been broken because of the special form of the public polynomials. There are some other designs, which are reviewed below, that are all broken.
Previous Work in Multivariate Cryptography
The outline of a public-key cryptosystem based on iterative polynomial substitution is discussed by H. Fell et al., in “Analysis of a public key approach based on polynomial substitution,” Adv. Cryptol.—CRYPTO'85, 1986, vol. 218, Lecture Notes in Computer Science, pp. 340-349. The idea is attractive and simple, but as the authors mention, the number of terms in polynomials astronomically increase even after a few iterations. A few solutions are provided to limit the number of terms, but some solutions are not very practical and none of them gives an efficient cryptosystem.
The idea of using homogenous quadratic polynomials as the public information is discussed by T. Matsumoto et al., in “Public quadratic polynomial-tuples for efficient signature-verification and message-encryption,” Adv. Cryptol.—EUROCRYPT'88, Berlin, Germany, 1988. To generate the public polynomials, an invertible quadratic monomial over GF(qn), a degree n extension field of GF(q), is chosen. Here, q is a power of 2. The field GF(q) can be considered as an n-dimensional vector space over GF(q). Using basis vectors, the quadratic monomial is converted to n quadratic homogenous polynomials in n variables. The encryption is performed by evaluating public polynomials at the plaintext block. For decryption, the ciphertext block is transformed back to GF(qn) and the monomial is inverted. Unfortunately, this scheme has been broken because of some unexpected algebraic relations.
Two generalizations of this scheme, called hidden field equations (HFE) and isomorphisms of polynomials (IP) were developed. The HFE scheme has been broken. The attack uses the simple fact that every quadratic homogenous multivariate polynomial has a matrix representation. Using this representation, a highly overdefined system of quadratic homogenous equations in the secret information is obtained. A new technique called relinearization for solving such systems was proposed by Kipnis. Running numerous experiments showed that this technique for solving overdefined systems of homogenous quadratic polynomials is not as efficient as one may expect. Hence, it was improved as XL and FXL algorithms. These algorithms are efficient only when the number of polynomial equations is proportional to the square of the number of unknown variables.
Other attacks on the HFE scheme have been developed. These attacks take advantage of the special format of the public polynomials. The latest attack on the HFE family is the fast algorithm of Faugere for computing Gröbner basis. It has been shown that the system of public polynomials of HFE can be solved in a reasonable time using this algorithm.
The signature scheme QUARTZ is based on a variant of HFE. QUARTZ can generate signatures of length 128 bits with the security level 280. The security of QUARTZ is studied by Courtois and some generic attacks are provided. The signature schemes FLASH and SFLASH are based on the C*—algorithm that can be regarded as a special case of the more general HFE scheme. It was claimed that these schemes can generate signatures of lengths 296 and 259 bits with the security level 280, respectively. However, SFLASH has been broken.
A signature scheme based on birational permutations is based on using a quadratic homogenous tame automorphism and hiding its coefficients by applying two affine transforms one at the input and one at the output. The public key in this scheme consists of a number of multivariate quadratic polynomials over the ring Zn where n=pq is a positive composite integer consisting of two distinct large prime factors p and q. Although the security of this scheme is based on the integer-factorization problem, it can be regarded as a multivariate cryptographic scheme because of its structure. This scheme has been broken by Coppersmith.
A public-key cryptosystem and signature scheme based on the composition of four tame automorphisms, called tame transformation method (TTM), was introduced by Moh. This scheme was broken by Goubin where the cryptanalysis is reduced to an instance of the MinRank problem that can be solved in feasible time.